package 剑指offer.双指针法;

/**
 * 给一个链表找到他的倒数第 k 个节点
 * <p>
 * 很容易想到的办法就是先遍历一遍确定有多少个节点，然后倒数第 k 个节点就是第 n-k+1 处的节点
 *
 * 显然效率低下，需要使用双指针法：
 * p1 指向头结点
 * p2 指向头结点后面第 k 个节点
 * p1 与 p2 之间保持 k-1 的距离
 * 当 p2 指向最后面的时候 p1 指向第 k 个节点
 */
public class 第22题链表中倒数第K个节点 {

    class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k == 0) {
            return null;
        }
        ListNode p1 = head;
        ListNode p2 = head;
        for (int i = 0; i < k - 1; i++) {
            if (p2.next != null){
                p2 = p2.next;
            } else {
                return null;
            }
        }
        while (p2.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}
